Due to its decentralized nature, Federated Learning (FL) lends itself to adversarial attacks in the form of backdoors during training. The goal of a backdoor is to corrupt the performance of the trained model on specific sub-tasks (e.g., by classifying green cars as frogs). A range of FL backdoor attacks have been introduced in the literature, but also methods to defend against them, and it is currently an open question whether FL systems can be tailored to be robust against backdoors. In this work, we provide evidence to the contrary. We first establish that, in the general case, robustness to backdoors implies model robustness to adversarial examples, a major open problem in itself. Furthermore, detecting the presence of a backdoor in a FL model is unlikely assuming first-order oracles or polynomial time.

The focus of the submission is backdoor attacks in federated learning. The authors 1) show that models prone to adversarial corruptions are also vulnerable to backdoor attacks, 2) prove that detecting backdoors can be hard, and 3) propose a new class of backdoor attacks called edge-case backdoors. The theoretical contributions are accompanied with extensive evaluation of the new backdoor attack on challenging datasets. The paper is technically sound, it focuses on a current topic of machine learning and delivers both important theoretical insights and new algorithmic tools. It can be of interest to the NeurIPS audience.

Weaknesses: Major Concerns 1. D_edge - I have some concerns w.r.t the backdoors injected via D_edge (i.e., data from tail end of some distribution). But, wouldn't essentially any set of data outside from MNIST display similar statistics (e.g., CIFAR, EMNIST) -- possible even adversarially crafted data? But more generally, I find constructing the p-edge-case dataset in the paper loosely defined. Because almost always in the paper, D' is defined as D \cap D_edge. I was expecting it to be mixed only with a particular data partition D_i.

Due to its decentralized nature, Federated Learning (FL) lends itself to adversarial attacks in the form of backdoors during training. The goal of a backdoor is to corrupt the performance of the trained model on specific sub-tasks (e.g., by classifying green cars as frogs). A range of FL backdoor attacks have been introduced in the literature, but also methods to defend against them, and it is currently an open question whether FL systems can be tailored to be robust against backdoors. In this work, we provide evidence to the contrary. We first establish that, in the general case, robustness to backdoors implies model robustness to adversarial examples, a major open problem in itself. Furthermore, detecting the presence of a backdoor in a FL model is unlikely assuming first-order oracles or polynomial time.